package leetcode_题库;

import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/8/17 10:13
 */
public class _977_有序数组的平方 {
    public static void main(String[] args) {
        int[] nums = new int[]{-7,-3,2,3,11};
        System.err.println(Arrays.toString(getArraySquare(nums)));
        
    }

    private static int[] getArraySquare(int[] nums) {
        int lp = 0;
        int rp = nums.length - 1;
        //双指针平方
        if (nums.length % 2 == 1){
            nums[nums.length / 2] *= nums[nums.length / 2];
        }
        while (lp < rp){
            nums[lp] *= nums[lp++];
            nums[rp] *= nums[rp--];
        }
        //排序（就别自己写API啦！）
        Arrays.sort(nums);
//        quickSort(nums,0,nums.length - 1);
        return nums;
    }

    private static void quickSort(int[] nums,int start,int end) {
        if (start >= end){
            return;
        }
        //选择基准元素
        int pivot = nums[start];
        //定义左右哨兵，左哨兵站在pivot上，不动
        int ls = start;
        int rs = end;
        while (ls < rs){
            //右哨兵左移，只要比边界值大且不小于pivot，就一只移动
            while (rs > start){
                if(nums[rs] < pivot){
                    break;
                }
                rs--;
            }
            //左哨兵右移
            while (ls < rs){
                if (nums[ls] > pivot){
                    swap(nums,ls,rs);
                    break;
                }
                ls++;
            }
        }
        //交换初始值和相遇值
        swap(nums,start,ls);
        //交换pivot和哨兵占位
        //递归
        quickSort(nums,start,ls - 1);
        quickSort(nums,ls + 1,end);
    }

    private static void swap(int[] nums, int ls, int rs) {
        if (ls == rs){
            return;
        }
        nums[ls] ^= nums[rs];
        nums[rs] ^= nums[ls];
        nums[ls] ^= nums[rs];
    }
}
